
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static int solution(int n, int k, int[] data) {
        // 如果k >= n，可以在第一天购买所有需要的食物
        if (k >= n) {
            int min = data[0];
            for (int num : data) {
                if (num < min) min = num;
            }
            return min * n;
        }

        Deque<int[]> mins = new ArrayDeque<>();
        int result = 0;

        for (int j = 0; j < n; j++) {
            // 维护单调队列，确保队列中的元素是递增的
            while (!mins.isEmpty() && mins.peekLast()[1] > data[j]) {
                mins.pollLast();
            }
            // 将当前元素加入队列
            mins.offer(new int[]{j, data[j]});
            // 移除窗口外的元素
            while (mins.peekFirst()[0] <= j - k) {
                mins.pollFirst();
            }
            // 累加当前窗口的最小价格
            result += mins.peekFirst()[1];
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试样例
        System.out.println(solution(5, 2, new int[]{1, 2, 3, 3, 2}) == 9);
        System.out.println(solution(6, 3, new int[]{4, 1, 5, 2, 1, 3}) == 9);
        System.out.println(solution(4, 1, new int[]{3, 2, 4, 1}) == 10);
        // 测试k >= n的情况
        System.out.println(solution(4, 4, new int[]{3, 2, 4, 1}) == 4);
        System.out.println(solution(4, 5, new int[]{3, 2, 4, 1}) == 4);
    }
}

